import functools


class Solution(object):
    def maxProduct(self, s):
        n = len(s)

        def find_max(t):
            if not t:
                return 0
            else:
                @functools.cache
                def dfs(i, j):
                    if i > j:
                        return 0
                    if i == j:
                        return 1
                    else:
                        if t[i] == t[j]:
                            return 2 + dfs(i + 1, j - 1)
                        else:
                            return max(dfs(i + 1, j), dfs(i, j - 1))

                return dfs(0, len(t) - 1)

        max_val = 0

        def cal(val):
            t1 = []
            t2 = []
            for i in range(n):
                if (val >> i) & 1:
                    t1.append(s[i])
                else:
                    t2.append(s[i])
            return find_max(t1) * find_max(t2)

        for val in range(1, 2 ** n - 1):
            max_val = max(max_val, cal(val))
        return max_val